Enterprises have become increasingly dependent on computer network infrastructures to provide services and accomplish mission-critical tasks. Indeed, the performance and efficiency of these network infrastructures have become critical as enterprises increase their reliance on distributed computing environments and wide area computer networks. The widely-used TCP/IP protocol suite, which implements the world-wide data communications network environment called the Internet and is employed in many local area networks, omits any explicit supervisory function over the rate of data transport over the various devices that comprise the network. While there are certain perceived advantages, this characteristic has the consequence of juxtaposing very high-speed packets and very low-speed packets in potential conflict and produces certain inefficiencies. Certain loading conditions degrade performance of networked applications and can even cause instabilities which could lead to overloads that could stop data transfer temporarily. The above-identified U.S. Patents and patent applications provide explanations of certain technical aspects of a packet based telecommunications network environment, such as Internet/Intranet technology based largely on the TCP/IP protocol suite, and describe the deployment of bandwidth management solutions to monitor and manage network environments using such protocols and technologies.
The Transmission Control Protocol (TCP) provides connection-oriented services for the protocol suite's application layer—that is, the client and the server must establish a connection to exchange data. TCP transmits data in segments encased in IP datagrams, along with checksums, used to detect data corruption, and sequence numbers to ensure an ordered byte stream. TCP is considered to be a reliable transport mechanism because it requires the receiving host to acknowledge not only the receipt of data but also its completeness and sequence. If the sending host does not receive notification from the receiving host within an expected time frame, the sending host times out and retransmits the segment.
TCP uses a sliding window flow-control mechanism to control the throughput over wide-area networks. As the receiving host acknowledges initial receipt of data, it advertises how much data it can handle, called its window size. The sending host can transmit multiple packets, up to the advertised window size, before it stops and waits for an acknowledgment. The sending host transmits data packets up to the advertised window size, waits for acknowledgement of the data packets, and transmits additional data packets.
TCP's congestion-avoidance mechanisms attempt to alleviate the problem of abundant packets filling up router queues. TCP's slow-start algorithm attempts to take full advantage of network capacity. TCP increases a connection's transmission rate using the slow-start algorithm until it senses a problem and then it backs off. It interprets dropped packets and/or timeouts as signs of congestion. The goal of TCP is for individual connections to burst on demand to use all available bandwidth, while at the same time reacting conservatively to inferred problems in order to alleviate congestion. Specifically, while TCP flow control is typically handled by the receiving host, the slow-start algorithm uses a congestion window, which is a flow-control mechanism managed by the sending host. With TCP slow-start, when a connection opens, only one packet is sent until an ACK is received. For each received ACK, the sending host doubles the transmission size, within bounds of the window size advertised by the receiving host. Note that this algorithm introduces an exponential growth rate. The TCP transmitter increases a connection's transmission rate using the slow-start algorithm until it senses a problem and then it backs off. It interprets dropped packets and/or timeouts as signs of congestion. Once TCP infers congestion, it decreases bandwidth allocation rates.
Given the congestion control mechanisms employed by TCP end systems, a crude form of bandwidth management in TCP/IP networks (that is, policies operable to allocate available bandwidth from a single logical link to network flows) is accomplished by a combination of TCP end systems and routers which queue packets and discard packets when some congestion threshold is exceeded. The discarded and therefore unacknowledged packet serves as a feedback mechanism to the TCP transmitter. Routers support various queuing options to provide for some level of bandwidth management. These options generally provide a rough ability to partition and prioritize separate classes of traffic. However, configuring these queuing options with any precision or without side effects is in fact very difficult, and in some cases, not possible. Seemingly simple things, such as the length of the queue, have a profound effect on traffic characteristics. Discarding packets as a feedback mechanism to TCP end systems may cause large, uneven delays perceptible to interactive users. Moreover, while routers can slow down inbound network traffic by dropping packets as a feedback mechanism to a TCP transmitter, this method often results in retransmission of data packets, wasting network traffic and, especially, inbound capacity of a WAN link. In addition, routers can only explicitly control outbound traffic and cannot prevent inbound traffic from over-utilizing a WAN link. A 5% load or less on outbound traffic can correspond to a 100% load on inbound traffic, due to the typical imbalance between an outbound stream of acknowledgments and an inbound stream of data.
In response, certain data flow rate control mechanisms have been developed to provide a means to control and optimize efficiency of data transfer as well as allocate available bandwidth among a variety of business enterprise functionalities. Such network devices, including PacketShaper® application traffic management appliance offered by Packeteer®, Inc. of Cupertino, Calif., are typically deployed at strategic points in enterprise networks to monitor and control data flows traversing, for example, a WAN link. For example, U.S. Pat. No. 6,038,216 discloses a method for explicit data rate control in a packet-based network environment without data rate supervision. Data rate control directly moderates the rate of data transmission from a sending host, resulting in just-in-time data transmission to control inbound traffic and reduce the inefficiencies associated with dropped packets. Bandwidth management devices allow for explicit data rate control for flows associated with a particular traffic classification. Bandwidth management devices allow network administrators to specify policies operative to control and/or prioritize the bandwidth allocated to individual data flows according to traffic classifications. In addition, certain bandwidth management devices, as well as certain routers, allow network administrators to divide available bandwidth into partitions. With some network devices, these partitions can be configured to ensure a minimum bandwidth and/or cap bandwidth as to a particular class of traffic. An administrator specifies a traffic class (such as FTP data, or data flows involving a specific user) and the size of the reserved virtual link—i.e., minimum guaranteed bandwidth and/or maximum bandwidth. Such partitions can be applied on a per-application basis (protecting and/or capping bandwidth for all traffic associated with an application) or a per-user basis (protecting and/or capping bandwidth for a particular user). In addition, certain bandwidth management devices allow administrators to define a partition hierarchy by configuring one or more partitions dividing the access link and further dividing the parent partitions into one or more child partitions.
The PacketShaper® application traffic management appliance, in certain of its implementations, uses policies and partitions to determine how to allocate bandwidth for individual data flows. When determining bandwidth allocation, the appliance takes into account all bandwidth demands and uses the following basic allocation scheme:                Traffic flows that have assigned guaranteed rates are satisfied first;        All other traffic—traffic with and without assigned policies and unclassified traffic—competes for the remaining bandwidth (called excess bandwidth);        Excess bandwidth is proportionately allocated based on the priorities in priority and rate policies;        Flows from traffic classes with partitions are given more bandwidth (or less) to satisfy those partitions' minimum (or maximum) rates. In certain application traffic management devices, an initial rate demand estimate is made for each rate-controlled flow based on the detected link capacity of the path between the client and server. U.S. Pat. No. 5,802,106 discloses methods and systems directed to estimating the effective rate capacity of the communications path between two TCP end systems. This initial rate demand estimate is used in bandwidth allocation determinations and becomes the target rate of the data flow subject to partition and policy limits. For example, when the appliance encounters a data flow, which matches a traffic class that includes a partition, it allocates bandwidth to that flow based on the number of current flows, and their respective target rates, subject to the partition. If the initial rate demand estimate does not exceed this allocation, it sets the target rate to the initial rate demand estimate.        
In the case of short-lived flows (such as a data flow including a web page), however, the target rate may never be reached because of the TCP slow-start mechanisms discussed above. This circumstance results in certain inefficiencies resulting from unutilized bandwidth that goes un-used to satisfy other data flows. That is, the mechanisms for allocating bandwidth, by using this initial rate demand estimate, essentially over-allocate bandwidth to short-lived flows, as such flows terminate before the TCP slow-start mechanism allows them to ramp up to the estimated demand. These inefficiencies are exacerbated when the short-lived flows are also compressed (such as by a compression tunnel mechanism between the device allocating bandwidth and a second network device in the communications path), wherein the initial target rate is unachievable and the flow duration is too short for the unused bandwidth to be transferred to other data flows.
In light of the foregoing, a need in the art exists for methods, apparatuses and systems directed to bandwidth allocation mechanisms that adapt to TCP slow-start mechanisms. Embodiments of the present invention substantially fulfill this need.